The present invention relates in general to a digital processor, and more particularly, to a processor which is provided with a buffer storage.
A conventional computer attains high speed operation by executing a stream of instructions in a pipeline manner, i.e., in an overlapping manner. If a branch instruction appears in the stream, however, its processing performance drops because a disturbance occurs in the otherwise smooth flow of the pipeline operation. Therefore, in order to improve the processing performance of the computer, it is essential to process a branch instruction at a high speed.
To better understand this problem, various examples of branch instructions as provided in the IBM System/370 will be explained with reference to FIGS. 1A to 1D.
FIG. 1A shows the instruction format of a BCR instruction. This instruction branches to an instruction whose address is equal to the content of one of the general registers designated by an R.sub.2 field, if a condition code CC set within an arithmetic unit by a previous instruction satisfies the branch condition designated by a mask field (M1).
FIG. 1B shows the instruction format of a BC instruction. This instruction branches to an instruction whose address is equal to the sum of the contents of two of the general registers designated respectively by the X.sub.2 and B.sub.2 fields of the instruction and the value of the displacement field D.sub.2.
FIG. 1C shows the instruction format of a BALR instruction. This instruction stores the content of a present PSW (program status word containing the next instruction address) in one of the general registers designated by the R.sub.1 field, and branches to an instruction whose address is equal to the content of one of the general registers designated by the R.sub.2 field.
FIG. 1D shows the instruction format of a BAL instruction. This instruction stores the content of the present PSW in one of the general registers designated by the R.sub.1 field, and branches to an instruction whose address is equal to the sum of the contents of two general registers designated by the X.sub.2 and B.sub.2 fields and the value of the D.sub.2 field.
There are several other types of branch instructions, but for executing any such instruction, the processing performance of the computer drops because the smooth flow of the pipeline operation becomes disturbed due to the fact that some time lag inevitably occurs before a branch target instruction is fetched from the main storage after detection of the branch instruction. In order to execute the branch instruction at a high speed, therefore, the fetching of the branch target instruction must be speeded up.
A branch target instruction buffer storage was proposed for this purpose by the Horikoshi et al U.S. Pat. No. 3,940,741, which is assigned to the same assignee as the present invention. The buffer storage, referred to as a route memory by Horikoshi et al, comprises an associative memory which stores a target instruction when a branch is attained for the first time for each branch instruction and produces the following two outputs by use of the instruction address (IA) of a decoded instruction as a key when decoding each branch instruction thereafter:
(i) A target instruction (TI); and
(ii) An output (BA) indicating whether or not there is a high probability of fullfillment of a branch condition by the decoded branch instruction.
According to this prior art approach, a target instruction for a branch instruction need not be fetched from the main storage when the branch instruction is executed a second time since the target instruction is available in the faster route memory. However, we have recently found that the prior art target instruction buffer storage involves the following problem. Namely, since only the instruction address (IA) of the branch instruction is used as the key to make reference to the target instruction buffer storage, the target instruction buffer storage cannot handle a situation where one branch instruction branches to any one of a plurality of target instructions.
For example, considering the case shown in FIG. 2, the flow changes from a branch instruction 2004 in a main routine 2003 to the leading address of a sub-routine 2008, then returns to an instruction 2005 in the main routine 2003 at the completion of the BCR instruction 2009 of the sub-routine 2008. The flow then changes once again at a branch instruction 2006 to the same sub-routine 2008 and returns again to an instruction 2007 from the BCR instruction 2009 after completion of the sub-routine 2008. In this case, according to the prior art, the instruction 2005 and the address of the instruction 2005 are stored in the target instruction buffer storage, when the flow returns to the instruction 2005 from the BCR instruction 2009 for the first time. Thus, the flow cannot return to the instruction word 2007 on the basis of what is stored in the target instruction buffer storage, when the BCR instruction 2009 is executed the second time. In this example, F in the mask field of the BCR instruction 2009 shows that the branch should be effected unconditionally, i.e., independently of a condition code.
Another example of the problem will be explained with reference to FIG. 3, where the flow branches to one of the three sub-routines A, B or C from a BC instruction 3002 in the main routine 3000, depending on the value stored in a general register 5 whose content is determined by the conditions p.sub.1, p.sub.2 as shown by steps 3010, 3012 and 3014. Here it is assumed that 10,000 is stored in advance in the general register 5. In this case, the target address of the BC instruction 3002 changes to 10,100, 10,200 or 10,300 depending upon which value is set into the register 5, so that the target instruction buffer storage which uses only the instruction address as the key to the target instruction does not always provide a correct target instruction.
From the foregoing examples described with reference to FIGS. 2 and 3, it is apparent that the prior art is not capable of satisfactorily responding to all conditions of repeated branching or conditional branching, so that the prior art provides a less than complete solution to the problem of increased speed in the handling of branch instructions.